package DataStructure.array.swordOffer2;

/**
 * 剑指 Offer 03. 数组中重复的数字 https://leetcode.cn/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof
 */
public class FindRepeatNumber {

    /**
     * 思路：由于原数组中值小于n，故可通过取余的方式来编解码使一格可以存储两个信息
     */
    public int findRepeatNumber(int[] nums) {
        int n = nums.length;
        for(int i=0;i < nums.length;i++) {
            //通过编解码使一格可以存储两个信息
            int realNum = nums[i] % n;
            nums[realNum] += n;
        }
        for(int i=0;i < nums.length;i++) {
            if(nums[i] / n >= 2) {
                return i;
            }
        }
        return -1;
    }
}
